// 给定一个二叉树的根节点root,要求判断是否是一个有效的二叉搜索树
// 节点的左子树只包含 小于 当前节点的数， 节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。
// 思路1，递归，中序遍历，中序遍历下的二叉搜索树是递增的有序序列
function isValidBST(root) {
    // 记录上一轮的val，按照中序遍历，root.val肯定比上次记录的val大
    let maxVal = -Infinity
    function dfs(root) {
        if (!root) {
            return true
        }
        let left = dfs(root.left)
        if (root.val > maxVal) {
            maxVal = root.val
        } else {
            return false
        }
        let right = dfs(root.right)
        return left && right
    }
    return dfs(root)
}

// 思路2，中序遍历
function isValidBST2(root) {
    if (!root) {
        return true
    }
    let stack = []
    let cur = root
    let pre
    while (stack.length || cur) {
        if (cur) {
            stack.push(cur)
            cur = cur.left
        } else {
            let node = stack.pop()
            if (pre && pre.val >= node.val) {
                return false
            }
            pre = node
            cur = node.right
        }
    }
    return true
}
// 思路3，递归，前序遍历
function isValidBST3(root) {
    function dfs(root, minVal, maxVal) {
        if (!root) {
            return true
        }
        if (root.val <= minVal || root.val >= maxVal) {
            return false
        }
        return dfs(root.left, minVal, root.val) && dfs(root.right, root.val, maxVal)
    }
    return dfs(root, -Infinity, Infinity)
}

const root = {
    val: 4,
    left: {
        val: 3,
        left: {
            val: 8,
        },
        right: {
            val: 3.5,
            left: {
                val: 3.1
            }
        },
    },
    right: {
        val: 6,
    },
};

console.log(isValidBST(root))
console.log(isValidBST2(root))
console.log(isValidBST3(root))